In real-time graphics applications, such as games and physical simulations, numerous techniques are known to automatically generate models in the form of polygon meshes. Common generation techniques include laser range scanning and triangulation of implicit functions. Often, the resultant meshes include more polygons that can be rendered by standard rendering engines at real-time frame rates.
Therefore, in order to reduce the number of polygons in the models, multi-resolution triangle meshes are frequently used. These methods typically use two approaches for generating level-of-detail (LOD) meshes. In the static approach, a set of static LOD meshes are pre-computed before use in an application. At run-time, a member of the set is selected, based on viewing parameters and frame rate requirements, and displayed. In the dynamic approach, a single dynamic mesh is generated before use in the application, and then the mesh is adapted by a series of transformations according to the viewing parameters and the frame rate requirements, see Garland “Multiresolution Modeling: Survey and Future Opportunities,” Eurographics '99 State of the Art Reports, pp. 111-131, 1999.
Known dynamic meshing methods, such as view dependent progressive meshes (VDPM), and hierarchical dynamic simplification (HDS), generate hierarchical data structures that can be refined and decimated to reduce the number of polygons in the meshes. The hierarchy in the VDPM is formed by generating a new parent vertex for every pair of vertices combined by an edge collapse operation, see Hoppe “View-Dependent Refinement of Progressive Meshes,” Proceedings of SIGGRAPH 1997, pp. 189-198, 1997. The HDS hierarchy is formed by spatially subdividing a scene into cells, and grouping vertices in each cell into a single representative vertex, see Luebke et al. “View-Dependent Simplification of Arbitrary Polygonal Environments,” Proceedings of SIGGRAPH 1997, pp. 199-208, 1997. In both methods, a screen space error and normal cones are used to determine when to refine and decimate the mesh.
However, these techniques can still produce more polygons than needed. Furthermore, their processing time is dependent on the number of polygons in the original model, which can be prohibitively slow for large models. Finally, these methods can produce poor quality models when the polygon count is small.
Therefore, there is a need to provide a method and system for automatically generating real-time dynamic meshes that match viewing parameters and desired frame rates.
The use of normal cones for determining visibility is known in the art, see Hoppe and Luebke et al. as described above. In both systems, normal cones are constructed from the initial geometry of the model and placed in a data structure such as an octree. There, the range, or spread, of normals in an octree cell is a function of where the geometry lies with respect to the octree grid. For example, a leaf cell of the octree can have a large spread of normals simply because the geometry within that cell has a large degree of curvature. This type of normal cone construction can cause a rendering engine to draw many more polygons than necessary because polygons that should be classified as invisible, e.g., back facing, are instead classified as visible since the polygons are grouped in a leaf cell with a large spread of normals indicating, erroneously, that they are visible.
Therefore, there is a need to provide a method for automatically generating detail directed visibility elements, e.g., detailed directed normal cones, that will more accurately classify geometry such as polygons according to visibility, thus avoiding unnecessary processing such as the rendering of polygons as described above.